home *** CD-ROM | disk | FTP | other *** search
/ Turnbull China Bikeride / Turnbull China Bikeride - Disc 2.iso / STUTTGART / LANG / SCHEME / GNU / JACALRC / jacal / DOC / lambda < prev    next >
Text File  |  1993-07-01  |  10KB  |  278 lines
  1.             ALGEBRA AND THE LAMBDA CALCULUS
  2.  
  3.                by Aubrey Jaffer
  4.  
  5. ABSTRACT: An algebraic system which includes Church's lambda calculus
  6. and currying is presented.  Closures, applications, and currying are
  7. implemented using variable elimination.
  8.  
  9. The usual connection made between the lambda calculus and algebra is
  10. to construct the integers using the lambda calculus and then construct
  11. algebraic (and other formulas) by Godelizing them.
  12.  
  13. The system described here reverses this connection by implementing the
  14. lambda calculus in an algebraic system.  It is used in the JACAL
  15. symbolic mathematics system and gives JACAL the ability to represent
  16. functions as members of the algebraic system.  All of the system's
  17. operations (including simplification) can then be applied to functions
  18. as easily as to expressions.
  19.  
  20.                ALGEBRAIC REPRESENTATION
  21.  
  22. Given an underlying representation for multivariate polynomials we
  23. can represent an equation as a multivariate polynomial with the
  24. understanding that the polynomial is equal to zero.  We can convert
  25. typical equations to this form by multiplying both sides by the
  26. denominators and then subtracting the left side from both sides.  For
  27. instance:
  28.  
  29.     f/(c+d) = (a-b)/g;
  30.  
  31. Yields:
  32.  
  33.     0 = (a - b) c + (a - b) d - f g
  34.  
  35. How to represent expressions?  The usual approach is to use a
  36. polynomial or a ratio of polynomials.  Instead, we will introduce a
  37. special variable "@", calling it the value variable.  The value of a
  38. polynomial involving @ is that polynomial "solved" for @.  For
  39. instance, the expression:
  40.  
  41.     -1 + x
  42.     ------
  43.     1 + x
  44.  
  45. is represented internally as:
  46.  
  47.     0 = -1 + x + (-1 - x) @
  48.  
  49. This allows us to represent irrational expressions as well:
  50.  
  51.               5
  52.     0 = -1 - y - @ - @ 
  53.  
  54. Is the root of a fifth degree polynomial.
  55.  
  56. For the rest of this paper the examples will not show @ if the values
  57. can be represented in usual mathematical notation without it (as JACAL
  58. does).
  59.  
  60.                  SUBSTITUTION
  61.  
  62. At this level of algebraic abstraction we do all operations using
  63. variable elimination.  Variable elimination is the process of
  64. combining n polynomial equations so that m variables do not appear in
  65. the (n-m) resulting equations (where n > m).  Common techniques used
  66. include resultants [1][2][4][5] and Groebner Bases [3][4][5].
  67.  
  68.     eliminate([a+c^2=b,b+c^2=2],[c]);
  69.  
  70. Yields:
  71.  
  72.     0 = 2 + a - 2 b
  73.  
  74. Common symbolic transformations can be done by constructing auxiliary
  75. polynomial equations and eliminating variables between them and the
  76. original polynomial equations.  The operation we are interested in for
  77. the next section is substitution.  We can substitute an expression for
  78. a variable by constructing an auxiliary equation of the variable and
  79. then eliminating that variable.  Suppose we want to substitute
  80. (a*x+b)^2 for g in g+1/g.  We construct the equation g=(a*x+b)^2
  81. and then:
  82.  
  83.     eliminate([g=(a*x+b)^2, g+1/g],[g]);
  84.  
  85.          4        3        2  2  2      3    3    4  4
  86.     1 + b  + 4 a b  x + 6 a  b  x  + 4 a  b x  + a  x
  87.     --------------------------------------------------
  88.                 2              2  2
  89.                b  + 2 a b x + a  x
  90.  
  91. Eliminate deals only with polynomial equations so remember that g+1/g
  92. internally is:
  93.  
  94.          2
  95.     0 = 1 + g  - g @
  96.  
  97. and similarly for the result.
  98.  
  99.                   FUNCTIONS
  100.  
  101. A similar approach to the use of @ can be used for arguments as well.
  102. We will name these arguments @1, @2, and so on.
  103.  
  104. Functions do not need to use all of their arguments.  However, in this
  105. system, a function must use at least one of its arguments.  With this
  106. constraint, the only difference between a function and an expression is
  107. the presence of @n variables.  Our functions can return either
  108. equations or expressions; those containing @ are expressions and those
  109. without, equations.
  110.  
  111. A function which ignores its first two arguments is
  112. lambda([x,y,z],1/z-z), which would be represented as
  113.  
  114.           2
  115.     1 - @3
  116.     -------
  117.       @3
  118.  
  119. These functions can freely mix bound and free variables.  The
  120. following expression, with free c and bound x and y,
  121.  
  122.     f : lambda([x,y],c*(y+x)/(y-x));
  123.  
  124. is simply:
  125.  
  126.     c @1 + c @2
  127.     -----------
  128.      - @1 + @2
  129.  
  130. We can now apply this function.  We don't have to always apply it to
  131. two arguments, we can apply it to just one also.  This is called
  132. "currying" an argument.  The application
  133.  
  134.     g : f(x);
  135.  
  136. substitutes x for @1 from the polynomial equation for f.  It also
  137. "bumps" @2 down to @1 (also by substitution).  This results in a new
  138. function of one argument:
  139.  
  140.     c x + c @1
  141.     ----------
  142.      - x + @1
  143.  
  144. It this function is applied to one argument (which is a non-function)
  145. the result will be a non-function.  For example g(a+b) yields:
  146.  
  147.     (- a - b) c - c x
  148.     -----------------
  149.        - a - b + x
  150.  
  151. This result is exactly the same as the result of applying f(x,a+b).
  152.  
  153.                ALPHA-CONVERSION
  154.  
  155. The above method is sufficient when the arguments to functions are not
  156. themselves functions.  But when applying functions to functions
  157. differences in the order of elimination produce different results.
  158. Consider applying @1-@2 to the arguments (@2, @1).  The result should
  159. be @2-@1.  But if we curry an argument we get @2-@2 -> 0 applied to
  160. @1.
  161.  
  162. This problem is similar to the inadvertent capture of free identifiers
  163. by macros in languages like C and Lisp.  The solution to this problem
  164. is called alpha-conversion in the lambda calculus and Hygenic Macro
  165. Expansion in a paper of that title by E.E.Kohlbecker, D.P.Friedman,
  166. M.Fellinson, and B.Duba [6].
  167.  
  168. Since the names of bound identifiers are unimportant we will
  169. substitute new names for those lambda variables for which we will
  170. later substitute arguments.  This eliminates possible conflicts between
  171. the variables bound in the current function and variables in its
  172. arguments (which are free relative to this function).
  173.  
  174. In the above example substitute :@1 for @1 and :@2 for @2 in @1-@2
  175. yielding :@1-:@2.  Now substitute @2 for :@1 and @1 for :@2.  This
  176. then yields the desired result @2-@1.
  177.  
  178. Currying an argument would substitute @2 for :@1 and @1 for :@2 in
  179. :@1-:@2 to produce @2-@1.  When this function is applied to the
  180. remaining argument, @1, the result is @2-@1 as before.
  181.  
  182.                 LAMBDA
  183.  
  184. A symmetrical situation to currying of arguments is binding a variable
  185. over a function.  lambda([y],lambda([x],x-y)) should yield the same
  186. function as lambda([y,x],x-y).  The trick here is to "bump up" any
  187. lambda variables in an expression when binding additional variables.
  188. To execute lambda([y],@1-y) we substitute @2 for @1 and then @1 for y.
  189.  
  190.              VECTORS AND MATRICES
  191.  
  192. Vector and matrix valued functions can be represented by vectors and
  193. matrices some of whose entries are lambda expressions.  Clearly a
  194. vector or matrix function applied to scalar arguments should return a
  195. vector or matrix with the same shape as the function.
  196.  
  197. The case of a scalar function applied vector arguments can work if the
  198. multiplication used by the function is of a type compatible with the
  199. arguments.  Inner product is commutative while matrix multiplication
  200. is not.  Another possiblity here is to have a mechanism for allowing
  201. lambda expressions to reference elements vector and matrix arguments.
  202.  
  203. The case of vector or matrix functions applied to vector or matrix
  204. arguments gets stickier.  Allowing only elements of the arguements to
  205. be operated on is one solution; Another is to incorporate the
  206. structure of the arguments inside the structure of the function or
  207. vice versa.
  208.  
  209.              DIFFERENTIAL ALGEBRA
  210.  
  211. These techniques can be extended to differential algebra as well.  In
  212. differential algebra the derivative of a variable, written v', can act
  213. as an variable in polynomials.  Derivatives of derivatives are also
  214. allowed and can be written v'' and so on.
  215.  
  216. When applying a function, each distinct derivative of a lambda
  217. variable with a corresponding argument requires that an equation be
  218. generated and that derivative variable be eliminated.  We equate the
  219. nth derivative variable with the nth total derivative of its
  220. corresponding argument.  For instance to apply the function @1'/@2' to
  221. (x^3,x) we
  222.  
  223.     eliminate([@1'/@2',@1'=(x^3)',@2'=(x)'],[@1',@2']);
  224.  
  225.        2
  226.     3 x
  227.  
  228. As illustrated by this example, differential operators are now as
  229. easily expressed as functions.  This worked well for the univariate
  230. case; what about multiple variables?  (@1'/@2')((x+y)^2,x) yields
  231.  
  232.     2 x x' + 2 x' y + (2 x + 2 y) y'
  233.     --------------------------------
  234.                    x'
  235.  
  236. We need to set y' to 0 to get the expected answer 2 x + 2 y.  But when
  237. we curry we need to have the differentials remain until all the lambda
  238. variables are consumed. (@1'/@2')((x+y)^2) gives
  239.  
  240.     2 x x' + 2 x' y + (2 x + 2 y) y'
  241.     --------------------------------
  242.                   @1'
  243.  
  244. We don't want to set x' and y' to 0 in the numerator because the
  245. result would be 0.  We don't know which differential until @1' is
  246. substituted for.  I think the solution here is to set to zero
  247. differentials occuring only in the numerator and only for those
  248. expressions containing no lambda variables or their derivatives.
  249.  
  250.                   CONCLUSION
  251.  
  252. I have shown how to implement functional abstraction (lambda),
  253. application and partial application (currying) in a system built on
  254. variable elimination from polynomials.
  255.  
  256.                  BIBLIOGRAPHY
  257.  
  258. [1] Bareiss, E.H.: Sylvester's identity and multistep
  259.     integer-preserving Gaussian elimination. Mathematics of
  260.     Computation 22, 565-578, 1968.
  261.  
  262. [2] Uspensky, J.V.: Theory of Equations
  263.     McGraw-Hill Book Co., Inc., 1948
  264.  
  265. [3] Thomas W. Dube: "The Structure of Polynomial Ideals and Groebner
  266.     Bases", SIAM JOURNAL ON COMPUTING, (19,4) (August 1990) pp. 750-773.
  267.  
  268. [4] Hoffmann, C. M.: Geometric and Solid Modeling: An Introduction.
  269.     Morgan Kaufmann Publishers, Inc. San Mateo, California, 1989
  270.  
  271. [5] Geddes, K.O., Czapor, S.R., Labahn, G.: Algorithms for Computer
  272.     Algebra. Kluwer Academic Publishers
  273.  
  274. [6] Hygenic Macro Expansion
  275.     E.E.Kohlbecker, D.P.Friedman, M.Fellinson, and B.Duba
  276.     1986 ACM Conference on Lisp and Functional Programming
  277.     Pages 151-159
  278.